package 字符串;

/**
 * https://www.nowcoder.com/practice/28eb3175488f4434a4a6207f6f484f47?tpId=295&tqId=732&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 * @author zuojie
 *
 */
public class _BM84_最长公共前缀 {

	public static void main(String[] args) {
		String[] strs = {"abca","abc","abca","abc","abcc"};
		_BM84_最长公共前缀 test = new _BM84_最长公共前缀();
		System.out.println(test.longestCommonPrefix(strs));
	}

	/**
	 * step 1：处理数组为空的特殊情况。
	 * step 2：因为最长公共前缀的长度不会超过任何一个字符串的长度，因此我们逐位就以第一个字符串为标杆，遍历第一个字符串的所有位置，取出字符。
	 * step 3：遍历数组中后续字符串，依次比较其他字符串中相应位置是否为刚刚取出的字符，如果是，循环继续，继续查找，如果不是或者长度不足，说明从第i位开始不同，前面的都是公共前缀。
	 * step 4：如果遍历结束都相同，最长公共前缀最多为第一个字符串。
	 */
	public String longestCommonPrefix (String[] strs) {
		int len = strs.length;
		//空字符串数组
        if(len == 0) return "";
        //遍历第一个字符串的长度
        String str = strs[0];
        for(int i = 0;i<str.length();i++) {
        	char temp = str.charAt(i);
        	//遍历后续的字符串
        	for(int j = 1;j < len;j++) {
        		//比较每个字符串该位置是否和第一个相同
        		if(i == strs[j].length()/*前置条件:后续字符串长度必须小于i*/ || strs[j].charAt(i) != temp) {
        			//不相同则结束
        			return str.substring(0,i);
        		}
        	}
        }
		return str;
    }
}
